/**
 * 1049. 最后一块石头的重量 II
 * https://leetcode-cn.com/problems/last-stone-weight-ii/
 */
public class Solutions_1049 {
    public static void main(String[] args) {
//        int[] stones = {2, 7, 4, 1, 8, 1};  // output: 1   {{1, 1, 2, 7}, {4, 8}}
//        int[] stones = {3, 3, 4, 6, 8, 8};  // output: 0   {{3, 3, 4, 6}, {8, 8}}
        int[] stones = {31, 26, 33, 21, 40};  // output: 5   {{40, 33}, {21, 26, 31}}

        int result = lastStoneWeightII(stones);
        System.out.println(result);
    }

    /**
     * 动态规划，将题目转化成背包问题
     * 将 stones 中的全部石头重量，分成两堆
     * 使两堆的石头重量之差，尽可能得小（即两堆石头中的重量，都与 half 接近）
     * 为什么分成两堆石头，且最终两堆石头碰撞后的结果即是最终结果？
     * - 题目本质是做加减法操作，分成两堆，即是找到被减数与减数，最终两数相减，即是结果
     * - 要想减数与被减数的差最小，那么一定是两个数都靠近，stones 总和的一半
     * - 即在 stones 中找到 1 个或多个石头，重量总和小于等于 stones 总和一半
     */
    public static int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        // 划分成两堆石头，那么两堆石头中的最大重量，只能是 sum / 2，结果向上取整
        int half = sum / 2;
        // dp[11] = 8，表示背包大小为 11 时，背包中最多放下重量为 8 的石头
        // 即 stones 中可以找到 1 个或多个重量和为 8 的石头
        // 且重量 8 是在 stones 中能够找到的小于等于 half 的最优解
        int[] dp = new int[half + 1];

        for (int stone : stones) {
//            for (int i = stone; i <= half; i++) {
            // 从大到小，而不是从小到大，因为每个石头只能够取用 1 次
            for (int i = half; i >= stone; i--) {
                // 动态规划，计算 dp[i] 能够装下的最大石头重量
                dp[i] = Math.max(dp[i], dp[i - stone] + stone);
            }
        }
        // 最终，有一堆石头的重量是 dp[half]，与另一堆石头重量 sum - dp[half] 碰撞，结果即是最后一个石子的重量
        return sum - 2 * dp[half];
    }
}
